package com.lin.codesnippet.sort;

import com.lin.enums.codesnippet.SortStatusCode;
import com.lin.codesnippet.sort.util.SortUtil;

/**
 * 堆排序
 * <p>O(nlogn)~O(nlogn)~O(nlogn)</p>
 * 不稳定
 *
 * @author linqiankun
 */
public class HeapSort {

    /**
     * 堆排序
     *
     * @param array          需要排序的数组
     * @param sortStatusCode 排序方式
     */
    public static void heapSorted(int[] array, SortStatusCode sortStatusCode) {
        // 建立一个最大堆
        int heapSize = buildHeap(array, array.length, sortStatusCode);
        // 堆（无序区）元素个数大于1，未完成排序
        while (heapSize > 1) {
            // 将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素
            // 此处交换操作很有可能把后面元素的稳定性打乱，所以堆排序是不稳定的排序算法
            SortUtil.swap(array, 0, --heapSize);
            // 从新的堆顶元素开始向下进行堆调整，时间复杂度O(logn)
            heapify(array, 0, heapSize, sortStatusCode);
        }
    }


    /**
     * 堆结构调整
     * 从A[i]向下进行堆调整
     *
     * @param array          堆数组
     * @param i              当前节点索引
     * @param size
     * @param sortStatusCode 排序方式
     */
    private static void heapify(int[] array, int i, int size, SortStatusCode sortStatusCode) {
        // 左孩子索引
        int leftChild = 2 * i + 1;
        // 右孩子索引
        int rightChild = 2 * i + 2;
        // 选出当前结点与其左右孩子三者之中的最大值
        int max = i;
        if (leftChild < size && sortStatusCode.getCode() == SortUtil.compare(array[max], array[leftChild]))
        // if (leftChild < size && array[leftChild] > array[max])
        {
            max = leftChild;
        }
        if (rightChild < size && sortStatusCode.getCode() == SortUtil.compare(array[max], array[rightChild]))
        // if (rightChild < size && array[rightChild] > array[max])
        {
            max = rightChild;
        }
        if (max != i) {
            // 把当前结点和它的最大(直接)子节点进行交换
            SortUtil.swap(array, i, max);
            // 递归调用，继续从当前结点向下进行堆调整
            heapify(array, max, size, sortStatusCode);
        }
    }

    /**
     * 构造堆
     * 建堆，时间复杂度O(n)
     *
     * @param array          堆数组
     * @param n              当前节点
     * @param sortStatusCode 排序方式
     * @return
     */
    private static int buildHeap(int[] array, int n, SortStatusCode sortStatusCode) {
        int heapSize = n;
        // 从每一个非叶结点开始向下进行堆调整
        for (int i = heapSize / 2 - 1; i >= 0; i--) {
            heapify(array, i, heapSize, sortStatusCode);
        }
        return heapSize;
    }


}
